package main

import (
	"fmt"
)

func exist(board [][]byte, word string) bool {
	for i, row := range board {
		for j, b := range row {
			if b == word[0] {
				point := [2]int{i, j}
				key := fmt.Sprintf("%d,%d", i, j)
				visited := map[string]struct{}{
					key: {},
				}
				if backtrack(board, word, [][2]int{point}, visited) {
					return true
				}
			}
		}
	}
	return false
}

func backtrack(board [][]byte, word string, track [][2]int, visited map[string]struct{}) bool {
	m := len(board)
	n := len(board[0])
	if len(visited) == len(word) {
		return true
	}
	var x, y int
	var nextPoints [][2]int
	var keys []string
	lastPoint := track[len(track)-1]
	// 上
	x = lastPoint[0]
	y = lastPoint[1] - 1
	key := fmt.Sprintf("%d,%d", x, y)
	if _, ok := visited[key]; y >= 0 && !ok {
		nextPoints = append(nextPoints, [2]int{x, y})
		keys = append(keys, key)
	}
	// 下
	y = lastPoint[1] + 1
	key = fmt.Sprintf("%d,%d", x, y)
	if _, ok := visited[key]; y < n && !ok {
		nextPoints = append(nextPoints, [2]int{x, y})
		keys = append(keys, key)
	}
	// 左
	x = lastPoint[0] - 1
	y = lastPoint[1]
	key = fmt.Sprintf("%d,%d", x, y)
	if _, ok := visited[key]; x >= 0 && !ok {
		nextPoints = append(nextPoints, [2]int{x, y})
		keys = append(keys, key)
	}
	// 右
	x = lastPoint[0] + 1
	key = fmt.Sprintf("%d,%d", x, y)
	if _, ok := visited[key]; x < m && !ok {
		nextPoints = append(nextPoints, [2]int{x, y})
		keys = append(keys, key)
	}

	expect := word[len(visited)]
	for i, point := range nextPoints {
		if board[point[0]][point[1]] != expect {
			continue
		}
		track = append(track, point)
		key := keys[i]
		visited[key] = struct{}{}
		if backtrack(board, word, track, visited) {
			return true
		}
		track = track[:len(track)-1]
		delete(visited, key)
	}
	return false
}

func main() {
	println(exist([][]byte{
		{'A', 'A', 'A', 'A', 'A', 'A'},
		{'A', 'A', 'A', 'A', 'A', 'A'},
		{'A', 'A', 'A', 'A', 'A', 'A'},
		{'A', 'A', 'A', 'A', 'A', 'A'},
		{'A', 'A', 'A', 'A', 'A', 'A'},
		{'A', 'A', 'A', 'A', 'A', 'A'},
	}, "AAAAAAAAAAAABAA"))
	//println(exist([][]byte{
	//	{'A', 'B', 'C', 'E'},
	//	{'S', 'F', 'C', 'S'},
	//	{'A', 'D', 'E', 'E'},
	//}, "ABCCED"))
}
